// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-04 20:42
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class TriangleNumberUpdate {
    /**
     * 使用双指针维护j 和 k
     */
    public int triangleNumber(int[] nums) {
        // 排序完之后数组内元素的顺序是递增的,所以随着j的右移nums[i] + nums[j] 的总和也在不断增加, 且k的值也在不断增加
        int n = nums.length;
        int ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            int k = i;
            for (int j = i + 1; j < n; j++) {
                while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
                    ++k;
                }
                ans += Math.max(k - j, 0);
            }
        }
        return ans;
    }

    @Test
    public void shout() {
        int[] nums = {2, 2, 3, 4};
        System.out.println(triangleNumber(nums));
    }


}
